package DataStructure.tree;

import java.util.HashMap;

/**
 * 105. 从前序与中序遍历序列构造二叉树 https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal
 */
public class BuildTree {

    HashMap<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        for(int i=0;i < inorder.length;i++) {
            map.put(inorder[i], i);
        }
        return buildTree(preorder, inorder, 0, inorder.length-1);
    }

    /**
     * 根据根节点值preorder[p]和中序遍历序列[i1, i2]构造树
     */
    private int p=0;
    public TreeNode buildTree(int[] preorder, int[] inorder, int i1, int i2) {
        if(i1 > i2) return null;
        int val = preorder[p++];//构造顺序就是根左右 故每构造一个节点后直接将p增1即可
        TreeNode root = new TreeNode(val);
        //找到根节点值在中序遍历序列中的位置，然后分别递归构造左子树和右子树
        int k = map.get(val);
        root.left = buildTree(preorder, inorder, i1, k-1);
        root.right = buildTree(preorder, inorder, k+1, i2);
        return root;
    }
}
